The present invention relates to a priority execution control method capable of processing as quick as possible a processing request which should be preferentially processed among a plurality of processing requests output from an application program, and an apparatus therefor.
Queues are generally used to absorb the difference between the processing request occurrence frequency per unit time and the processing amount per unit time in an information processing system. As shown in FIG. 17A, a plurality of processing requests 1102 generated in time-series from a processing request source 1101 such as an application program are temporarily stored in a queue 1103.
After the processing requests 1102 are stored in the queue 1103, a processor 1104 reads out one processing request 1102 from the queue 1103 in accordance with a FIFO (First-In First-Out) method. The processor 1104 performs processing in accordance with the contents of the processing request 1102, and outputs a processing result 1105. If another processing request 1102 remains in the queue 1103 after one processing request 1102 is processed, the processor 1104 similarly reads out the processing request 1102 and performs processing.
In FIG. 17A, the processing requests 1102 are sequentially processed in the generation order, and a specific processing request cannot be processed in preference to other processing requests. To preferentially execute a specific processing request, not a single queue but two, priority and normal queues are generally used. As shown in FIG. 17B, processing requests 1102 generated by the processing request source 1101 such as an application program are distributed to a priority queue 1107 and normal queue 1108 by a distributor 1106 in accordance with the processing priority.
The processor 1104 reads out the processing requests 1102 from the priority queue 1107 and normal queue 1108 in accordance with a predetermined rule, processes the processing requests 1102, and outputs processing results 1105. Assume that the predetermined rule is a rule that when a processing request exists in the priority queue 1107, the processing request is read out from the priority queue 1107, and only when no processing request exists, a processing request is read out from the normal queue 1108. In this case, a high-priority processing request 1102 stored in the priority queue 1107 is processed in preference to a processing request 1102 stored in the normal queue 1108.
A conventional priority execution control method using two, priority and normal queues is disclosed in Japanese Patent Laid-Open No. 4-176236 (reference 1). Reference 1 discloses a facsimile apparatus in which transmission data to which either normal or priority transmission is designated is stored in a priority or normal queue in accordance with the designation, transmission data is read out from the priority or normal queue in accordance with a preset ratio between priority communication and normal communication, and the transmission data is transmitted.
A similar priority execution control method is also adopted when a specific packet (e.g., audio packet) is preferentially transmitted by distributing the packet to a priority or normal queue in accordance with head information of the packet for the purpose of QoS (Quality of Service) in the path control apparatus of a packet communication network.
As a method of improving the performance of an information processing system, parallel processing is proposed. However, there is no application of the parallel processing technique to the priority execution control method using two, priority and normal queues. However, parallel operation of the processor 1104 shown in FIG. 17B would be achieved by an arrangement as shown in FIG. 17C. In FIG. 17C, processors 1104A and 1104B have the same function as that of the processor 1104 shown in FIG. 17B. That is, the processors 1104A and 1104B read out processing requests 1102 from the priority queue 1107 and normal queue 1108 in accordance with a predetermined rule, process the processing requests 1102, and output processing results 1105. Since processing means for processing the processing request 1102 operate parallel to each other, the processing amount per unit time increases in the information processing system.
In the priority execution control method shown in FIG. 17B, the probability of extracting the processing request 1102 from the priority queue 1107 is set higher than the probability of extracting the processing request 1102 from the normal queue 1108. A high-priority processing request 1102 stored in the priority queue 1107 can be processed in preference to a processing request 1102 stored in the normal queue 1108.
The following problem, however, arises when the priority queue 1107 is free and the normal queue 1108 stores one or more processing requests 1102. That is, if a high-priority processing request is stored in the priority queue 1107 after the processor 1104 extracts one processing request 1102 from the normal queue 1108 and starts processing, the high-priority processing request is not processed as quick as possible.
In this case, the problem cannot be solved by applying a top priority rule that when a processing request exists in the priority queue 1107, the processing request is read out from the priority queue 1107, and only when no processing request exists, a processing request is read out from the normal queue 1108. This is because when a high-priority processing request is stored in the priority queue 1107, the processor 1104 has executed a processing request extracted from the normal queue 1108, and cannot extract the processing request from the priority queue 1107 unless the current processing ends.
The same problem also occurs in an arrangement in which processors are arranged parallel to each other, as shown in FIG. 17C. If a high-priority processing request is stored in the blank priority queue 1107 while the processors 1104A and 1104B process one processing request 1102 from the normal queue 1108, the high-priority processing request is not processed until either of the processors 1104A and 1104B ends the processing of the current processing request.